/**
 * 691. 贴纸拼词
 * https://leetcode.cn/problems/stickers-to-spell-word/
 */

const codeA = 'a'.charCodeAt(0);

function dp(stickers, target, memory, mask) {
  if (memory[mask] < 0) {
    let res = target.length + 1;
    for (let i = 0; i < stickers.length; i += 1) {
      const sticker = stickers[i];
      let left = mask;
      const cnt = new Array(26).fill(0);
      for (let j = 0; j < sticker.length; j += 1) {
        cnt[sticker.charCodeAt(j) - codeA] += 1;
      }
      for (let j = 0; j < target.length; j += 1) {
        const index = target.charCodeAt(j) - codeA;
        if (((mask >> j) & 1) === 1 && cnt[index] > 0) {
          cnt[index] -= 1;
          left ^= 1 << j;
        }
      }
      if (left < mask) {
        res = Math.min(res, dp(stickers, target, memory, left) + 1);
      }
    }
    memory[mask] = res;
  }
  return memory[mask];
}

/**
 * @param {string[]} stickers
 * @param {string} target
 * @return {number}
 */
function minStickers(stickers, target) {
  const memory = new Array(2 ** target.length).fill(-1);
  memory[0] = 0;
  const res = dp(stickers, target, memory, memory.length - 1);
  return res <= target.length ? res : -1;
}

console.log(minStickers(['with', 'example', 'science'], 'thehat') === 3);
console.log(minStickers(['notice', 'possible'], 'basicbasic') === -1);
console.log(minStickers(['these', 'guess', 'about', 'garden', 'him'], 'atomher') === 3);
